﻿B3618 寻找团伙

题目描述
世界局势风云变幻，你想办一件大事。办事自然要有人参与，你能从 n 个人里面挑选一部分人共襄盛举。

要办这件事，一共涉及 k 方面的能力，例如游说他人的能力、玩游戏的能力、睡觉的能力。每位人士都会具备某一些能力，例如机器猫就可能擅长睡觉、擅长玩游戏，而不擅长游说他人。

你的计划很宏伟，因此你希望团队拥有很全面的能力。不幸的是，如果团队中有偶数个人拥有同一类能力，那么他们就会分成两派，争执不下，导致整个团队丧失这方面的能力。相应地，如果这项能力只有奇数个人拥有，那么他们总能形成一个多数派，帮团队去做这方面的工作。

需要注意的是，团队拥有的每一项能力，对计划的成功率的贡献是不一样的。第一项能力最重要，它的权重是 2
k−1
；第二项能力的权重是 2
k−2
；依次类推。第 k 项能力最不重要，权重只有 1。

计划的成功率得分，即是团队拥有的所有能力对应的权重之和。

你希望计划成功率最大。因此，你需要选出合适的人士，来参与到你的宏图伟业中。

输入格式
第一行，两个正整数 n, k。分别表示供你挑选的人的数量，以及能力的种类数。
接下来 n 行，每行表示每个人拥有的能力。这一行首先有一个整数 c，表示该人士拥有多少种能力；接下来是 c 个[1, k] 之间的正整数，表示该人士拥有哪些能力。

输出格式
仅一行，一个整数，表示计划的成功率得分。

输入输出样例
输入 #1复制

5 5
1 1
1 2
1 3
1 4
1 5
输出 #1复制

31
输入 #2复制

3 5
3 1 2 3
4 2 3 4 5
2 3 4
输出 #2复制

28
输入 #3复制

3 5
2 1 2
3 5 3 2
3 4 2 5
输出 #3复制

30
输入 #4复制

21 60
0
0
3 60 27 48
0
1 48
2 52 14
2 4 31
0
0
2 28 43
2 6 31
0
1 7
3 45 6 48
0
1 51
0
2 28 20
2 37 51
1 8
53 59 39 29 23 53 27 13 16 44 34 38 24 9 32 58 54 31 1 7 45 3 30 36 17 48 42 22 18 21 6 11 25 33 37 52 10 60 49 57 2 28 8 14 5 47 4 41 35 43 50 46 26 12
输出 #4复制

1152884121210322895
说明 / 提示
样例解释
第一组样例，共 5 个人，每个人拥有的能力不一样。最终选择的结果是让这 5 个人都参与计划，得分 16 + 8 + 4 + 2 + 1 = 31。

第二组样例，我们选择只让 1 参与。那么团队具有能力 1, 2, 3，得分 16 + 8 + 4 = 28。

第三组样例，我们让 1, 2, 3 参与。由于团队中有偶数个成员拥有能力 5，故团队并不拥有能力 5。奇数个成员拥有能力 2，故团队拥有能力 2。最终，团队具有能力 1, 2, 3, 4。得分 16 + 8 + 4 + 2 = 30。

数据规模与约定
对于 100 % 的数据，有 n≤21, k≤60。



//思路：每个组有n个人，能力相同的人在一组就会这个重复的能力变成0；因此想到异或；以及后面的价值关于2的多少次方，因此考虑到了
//位运算得到的，因此可以把每个人的能力位操作到一个ull类型的值上（k大于32）；保存起来，然后找这些人中的子集使得全部异或起来
//终值最大即可-->纯dfs问题 

#include<bits/stdc++.h> 
#define  IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
int n, k;
using ull = unsigned long long;//这里能力数量大于int类型位长度必须开ull 
ull value[26];
ull  final_ans = 0;//k大于了32，汇聚起这些能力--> 超int 
bool choice[26];

//dfs(pos) ：能完成从第pos个人的位置通过选与不选到最后一个人完成最终的ans的更新！ 
void dfs(int pos) {
	//递归出口
	if (pos == n) {
		ull middle_ans = 0;//k大于了32，汇聚起这些能力--> 超int 
		for (int j = 0; j < n; j++) {
			if (choice[j] == 0)continue;
			middle_ans ^= value[j];
		}
		final_ans = max(middle_ans, final_ans);//跟新最大值 
		return;
	}
	//主体
	//选pos处的人
	choice[pos] = 1;
	dfs(pos + 1);
	//不选pos处的人 
	choice[pos] = 0;
	dfs(pos + 1);

	//void 不用返回 
}
void dfs_solve() {

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		while (x--) {
			int v;
			cin >> v;
			value[i] |= 1ULL << (k - v);//1默认int加上ULL才识别unsigned long long-->正确进行位运算！ 
		}
	}

	dfs(0);
	cout << final_ans << endl;

}
int main() {
	IOS;
	dfs_solve();
	return 0;
}




